rtk 2002

2002.1.1 (dopolni)

1. podnaloga

Naročniki večjih količin tovora se običajno odločajo za prevoz tovora z ladjo. Ko zabojniki prispejo v luko, jih morajo tam uskladiščiti, vse dokler ponje ne pride naročnik ali pa jih morajo natovoriti na vlak. V neki luki zabojnike nalagajo enega ob drugega in ko zapolnijo celo vrsto, se lotijo nalaganja v drugo vrsto, nato tretjo in tako dalje. Ko se zapolni cela površina, začnejo zabojnike nalagati še na naslednjo višino v enakem zaporedju kot prej (torej prvi zabojnik na drugi višini pride položen na prvi zabojnik v prvi višini itd.). Podano imamo število zabojnikov v vsaki vrsti $n$, število vrst v vsaki plasti $m$ in število plasti $l$.

Naloga

Dopolni program zabojnik, ki za dane $n$, $m$ in $l$ ter za neko številko zabojnika izračuna, v kateri plasti in v kateri vrsti je ta zabojnik ter kateri v svoji vrsti je (stolpec). Vse troje se šteje od 1 naprej in to v takem vrstnem redu, da manjše številke predstavljajo tiste dele skladišča, ki so bili zapolnjeni prej. Mesto dopolnjevanja je označeno z ###.

def zabojnik(n,m,l,z):

    plast = 1 + (z - 1) / (n * m)
    vrsta = 1 + ((z - 1) ### (n * m)) ### n
    stolpec = 1 + ((z - 1) ### (n * m)) ### n

    izpis = 'Plast: ' + ### + ', '
    izpis += 'Vrsta: ' + ### + ', '
    izpis += 'Stolpec: ' + ###
    return izpis

Primer postavitve zabojev v plasteh za $n=4$, $m=3$, $l=2$:

| 1 2  3  4  |     | 13 14 15 16 |     | 25 26 27 28 |
| 5 6  7  8  |     | 17 18 19 20 |     | 29 30 31 32 |
| 9 10 11 12 |     | 21 22 23 24 |     | 33 34 35 36 |

Zabojnik s številko 16 na gornji sliki je četrti zabojnik v prvi vrsti druge plasti.

Vhodni podatki

Števila $m$,$n$,$l$ ter številka zabojnika, katerega položaj nas zanima.

Izhodni podatki

Položaj zabojnika (plast, vrsta, stolpec) v obliki niza.

Primer

Vhod

>>>>zabojnik(4,3,2,16)

Izhod

'Plast: 2, Vrsta: 1, Stolpec: 4'

Uradna rešitev

def zabojnik(n,m,l,z):

    plast = 1 + (z - 1) / (n * m)
    vrsta = 1 + ((z - 1) % (n * m)) / n
    stolpec = 1 + ((z - 1) % (n * m)) % n

    izpis = 'Plast: ' + str(int(plast)) + ', '
    izpis += 'Vrsta: ' + str(int(vrsta)) + ', '
    izpis += 'Stolpec: ' + str(int(stolpec))
    return izpis

2002.1.2 (dopolni)

1. podnaloga

Liliput je majhno mesto z veliko avtobusnimi postajami. Vse proge mestnih avtobusov so krožne. Vsaka postaja pa pripada natančno eni progi, torej nobena dva avtobusa nikoli ne obiščeta iste avtobusne postaje. Težava je v tem, da Liliputanci objavljajo vozne rede svojih avtobusov na prav poseben način. Avtobusne postaje so oštevilčene s števili od $1$ do $N$, opis vseh prog v njihovem mestu pa predstavijo kot zaporedje $N$ števil.

Za primer vzemimo zaporedje števil $[8, 10, 6, 3, 9, 4, 2, 5, 1, 7]$, ki ga lahko predstavimo kot:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 8 & 10 & 6 & 3 & 9 & 4 & 2 & 5 & 1 & 7 \end{pmatrix}$

Prvo število v zaporedju je $8$, kar pomeni, da gre avtobus, ki odpelje s postaje $1$, na postajo $8$. Osmo število v zaporedju je 5, kar pomeni, da avtobus, ki pripelje na postajo številka $8$, nadaljuje svojo pot do postaje številka $5$; peto število je $9$, zato avtobus nadaljuje pot do postaje $9$ in tako naprej, dokler se ne vrne na začetno postajo. Iz gornjega zaporedja lahko po tem postopku izluščimo tri krožne avtobusne proge: $[1, 8, 5, 9], [2, 10, 7], [3, 6, 4]$

Naloga

Tvoja naloga je dopolniti program avtobus, ki bo nevajenemu tujcu za poljubno zaporedje števil izpisal vse proge mestnih avtobusov ter mu povedal, koliko postaj ima najdaljša proga. Na voljo je seznam dolžine $N$, ki vsebuje poljubno zaporedje števil, ki ustreza opisu prog mestnih avtobusov. Mesto dopolnjevanja je označeno z ###.

def avtobus(vozni_red):

    N = len(vozni_red)
    obiskane_postaje = [False for i in range(N)]
    najdaljsa_proga = 0
    proge = []

    for j in range(N):
        if ###:
            obiskane_postaje[j] = True
            proga = [j+1]
            k = vozni_red[j]
            while ###:
                proga.append(k)
                obiskane_postaje[k-1] = True
                k = ###
            proge.append(proga)

        if len(proga) > najdaljsa_proga:
            najdaljsa_proga = len(proga)
    ###
    return proge

Vhodni podatki

Zaporedje števil, podano v seznamu.

Omejitve vhodnih podatkov

• $1 \leq N \leq 10^6$
  $N$ = število postaj

Izhodni podatki

Seznam z vsemi avtobusnimi programi predstavljenimi kot seznam postaj. Zadnji element seznama pa je dolžina najdaljše proge.

Primer

Vhod

>>>>avtobus([8, 10, 6, 3, 9, 4, 2, 5, 1, 7])

Izhod

[[1, 8, 5, 9], [2, 10, 7], [3, 6, 4], 4]

Uradna rešitev

def avtobus(vozni_red):

    N = len(vozni_red)
    obiskane_postaje = [False for i in range(N)]
    najdaljsa_proga = 0
    proge = []

    for j in range(N):
        if not obiskane_postaje[j]:
            obiskane_postaje[j] = True
            proga = [j+1]
            k = vozni_red[j]
            while k != j+1:
                proga.append(k)
                obiskane_postaje[k-1] = True
                k = vozni_red[k-1]
            proge.append(proga)

        if len(proga) > najdaljsa_proga:
            najdaljsa_proga = len(proga)
    proge.append(najdaljsa_proga)
    return proge

2002.1.3 (dopolni)

1. podnaloga

Pri uporabi bančne kartice moramo dokazati, da poznamo kodo pin (osebno identifikacijsko številko). Podobno v deželi PinLand uporabljajo štirimestne črkovne kode pin tudi za dostop do pomembnih podatkov na mreži. Pri razbijanju kode pin si pomagajmo s poskušanjem: vemo, kakšne so dovoljene kode, in preizkusimo vse možnosti.

Za testiranje je na voljo funkcija test, ki sprejme kodo v obliki niza in vrne True če je koda pravilna ter False če ni.

Za kodo pin veljata naslednji omejitvi:

• dolga je točno štiri znake;
• dovoljeni so le znaki A, . . . , Z, torej ravno vse velike črke angleške abecede.

Naloga

Dopolni program pin, ki bo s poskušanjem odkril pravo kodo pin in jo izpisal. Mesto dopolnjevanja je označeno z ###.

def pin():
    '''Funkcija s pomočjo funkcije test in poskušanjem najde pravo pin in jo izpiše.'''

    mozni_znaki = 'ABCDEFGHI###STUVWXYZ'
    poskus = [0,0,0,0]
    for a in mozni_znaki:
        poskus[0] = ###
        for b in mozni_znaki:
            ### = b
            for c in mozni_znaki:
                ###
                ###
                    ###

                    poskus_str = ''.join(poskus)
                    if test(poskus_str):
                        return poskus_str

Vhodni podatki

Funkcija nima vhodnega podatka.

Izhodni podatki

Niz štirih znakov, ki predstavljajo pravo pin kodo.

Uradna rešitev

def test(poskus):
    '''Funkcija vrne True, če je pin pravilen in False sicer.'''

    st = [66,90,88,65,78,30]
    stevec = 0
    for i in poskus[::-1]:
        a = ord(i)
        if a == st[stevec]:
            stevec += 1
        else:
            return False
    return True


def pin():
    '''Funkcija s pomočjo funkcije test in poskušanjem najde pravo pin in jo izpiše.'''

    mozni_znaki = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    poskus = [0,0,0,0]
    for a in mozni_znaki:
        poskus[0] = a
        for b in mozni_znaki:
            poskus[1] = b
            for c in mozni_znaki:
                poskus[2] = c
                for d in mozni_znaki:
                    poskus[3] = d

                    poskus_str = ''.join(poskus)
                    if test(poskus_str):
                        return poskus_str

2002.1.4 (dopolni)

1. podnaloga

Janez se odpravlja na pot z avtomobilom iz Ljubljane v Bruselj. Na poti bo moral večkrat doliti gorivo. Ker je cena goriva na bencinskih črpalkah različna, ga zanima, kako naj v Bruselj pride kar najceneje.

Na voljo ima naslednje podatke:

• dolžina poti (recimo 1200 km);
• velikost posode za gorivo (recimo 60 l);
• poraba goriva (recimo 7 litrov na 100 km);
• število črpalk ob poti;
• za vsako črpalko tudi njen položaj na poti (oddaljenost od Ljubljane v kilometrih) in ceno bencina na njej. (Vse cene so izražene v isti valuti.)

Janez pot začne s prazno posodo, prva črpalka pa je že takoj na začetku poti. Cilj potovanja predstavimo kot črpalko, kjer lahko Janez gorivo dobi zastonj.

Naloga

Dopolni program natoci_gorivo, ki za poljubno razporeditev črpalk in cene bencina ugotovi, kje in koliko goriva je treba doliti, da ga ne bo nikjer zmanjkalo, obenem pa bomo za gorivo porabili čim manj denarja. Mesto dopolnjevanja je označeno z ###.

def natoci_gorivo(pot, posoda, poraba, crpalke):
    '''Funkcija izračuna koliko goriva moramo dotočiti na kateri črpalki, da
    bo strošek goriva na naši poti najmanjši.'''

    # definiramo dve funkciji zgolj na račun bolj pregledne kode
    def oddaljenost(n):
        '''vrne oddaljenost n-te črpalke'''
        return crpalke[n-1][1]

    def cena(n):
        '''vrne ceno goriva na n-ti črpalki'''
        return crpalke[n-1][2]

    gorivo = 0
    st_crpalk = ###
    tocenje_goriva = []
    i = 1

    while i < st_crpalk:
        j = i + 1

        #poiščemo naslednjo najcenejšo črpalko
        while j < st_crpalk:
            if cena(j) ### cena(i):
                break
            else:
                j += 1

        # koliko goriva potrebujemo do naslednje cenejše črpalke
        if j > st_crpalk:
            razdalja = pot - oddaljenost(i)
        else:
            razdalja = oddaljenost(j) - ###

        potrebna_kolicina_goriva = round(###, 2)
        if gorivo < potrebna_kolicina_goriva:      # moramo dotočiti
            if potrebna_kolicina_goriva <= posoda: # dotočimo dovolj za pot do j-te črpalke
                dotocimo = round(###,2)
                znesek = round(###, 2)
                tocenje_goriva.append([i, dotocimo, znesek])
                gorivo = 0
                i = j
            else:     # natocimo poln tank, a ne bo dovolj do j-te črpalke
                dotocimo = round(###, 2)
                znesek = round(###, 2)
                tocenje_goriva.append([i, dotocimo, znesek])
                gorivo = posoda - round(((oddaljenost(i+1) - oddaljenost(i)) / 100) * poraba, 2)
                i += 1
        else:  # imamo dovolj do j-te črpalke
            gorivo -= ###
            i = j
    return tocenje_goriva

Vhodni podatki

Dolžina poti Velikost posode za gorivo Poraba goriva Seznam seznamov, ki predstavljajo bencinske črpalke: [stevilka, oddaljenost, cena].

Izhodni podatki

Seznam seznamov, ki povedo, koliko goriva mora Janez natočiti na kateri črpalki ter ceno iztočenega goriva: [stevilka, kolicina goriva, znesek za placilo]

Primer

Vhod

>>>>natoci_gorivo(150,50,7.5,[[1,0,1.8],[2,30,1.1],[3,150,0]])

Izhod

[[1, 2.25, 4.05], [2, 9.0, 9.9]]

Uradna rešitev

def natoci_gorivo(pot, posoda, poraba, crpalke):
    '''Funkcija izračuna koliko goriva moramo dotočiti na kateri črpalki, da
    bo strošek goriva na naši poti najmanjši.'''

    # definiramo dve funkciji zgolj na račun bolj pregledne kode
    def oddaljenost(n):
        '''vrne oddaljenost n-te črpalke'''
        return crpalke[n-1][1]

    def cena(n):
        '''vrne ceno goriva na n-ti črpalki'''
        return crpalke[n-1][2]

    gorivo = 0
    st_crpalk = len(crpalke)
    tocenje_goriva = []
    i = 1

    while i < st_crpalk:
        j = i + 1

        #poiščemo naslednjo najcenejšo črpalko
        while j < st_crpalk:
            if cena(j) < cena(i):
                break
            else:
                j += 1

        # koliko goriva potrebujemo do naslednje cenejše črpalke
        if j > st_crpalk:
            razdalja = pot - oddaljenost(i)
        else:
            razdalja = oddaljenost(j) - oddaljenost(i)

        potrebna_kolicina_goriva = round((razdalja / 100) * poraba, 2)
        if gorivo < potrebna_kolicina_goriva:      # moramo dotočiti
            if potrebna_kolicina_goriva <= posoda: # dotočimo dovolj za pot do j-te črpalke
                dotocimo = round(potrebna_kolicina_goriva - gorivo,2)
                znesek = round(dotocimo * cena(i), 2)
                tocenje_goriva.append([i, dotocimo, znesek])
                gorivo = 0
                i = j
            else:     # natocimo poln tank, a ne bo dovolj do j-te črpalke
                dotocimo = round(posoda - gorivo, 2)
                znesek = round(dotocimo * cena(i), 2)
                tocenje_goriva.append([i, dotocimo, znesek])
                gorivo = posoda - round(((oddaljenost(i+1) - oddaljenost(i)) / 100) * poraba, 2)
                i += 1
        else:  # imamo dovolj do j-te črpalke
            gorivo -= potrebna_kolicina_goriva
            i = j
    return tocenje_goriva